package com.czk.algorithm.dynamic.bag;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 可以拾取物品的一部分 （可以使用贪心，优先拾取性价比高的装备）
 *
 * @Author:ChenZhangKun
 * @Date: 2022/2/10 9:17
 */
public class DivisibleBag {
    public static void main(String[] args) {
        int capacity = 15;
        int[] weights = {1, 1, 2, 4, 12};
        int[] values = {1, 2, 2, 10, 4};
        System.out.println("背包最大价值：" + getHighestValue(capacity, weights, values));

    }

    public static double getHighestValue(int capacity, int[] weights, int[] values) {
        List<Item> list = new ArrayList<>();
        for (int i = 0; i < weights.length; i++) {
            // 添加
            list.add(new Item(weights[i], values[i]));
        }
        // 排序
        list = list.stream().sorted(Comparator.comparing(Item::getRatio).reversed()).collect(Collectors.toList());
        // 剩余背包最大容量
        int restCapacity = capacity;
        // 当前背包最大价值
        double highestValue = 0;
        for (Item item : list) {
            if (restCapacity >= item.value) {
                highestValue += item.value;
                restCapacity -= item.weight;
            } else {
                //背包装不下完整物品时，选择该件物品的一部分
                highestValue += (double) restCapacity / (double) item.weight * item.value;
                break;

            }
        }
        return highestValue;
    }

    public static class Item {
        private int weight;
        private int value;
        // 物品的性价比
        private double ratio;

        public Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
            this.ratio = (double) value / (double) weight;
        }

        public double getRatio() {
            return ratio;
        }
    }
}
